// 41.缺失的第一个正数
package LeetcodeHot100;

public class Solution041 {
    public int firstMissingPositive(int[] nums) {
        // 1. 将小于1的数设置为N+1
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= 0)
                nums[i] = nums.length + 1;
        }
        // 2. 如果当前元素为 x (1~N)，那么就将 nums[x-1] 设置为 -nums[x-1]，作为标记
        for (int i = 0; i < nums.length; i++) {
            int num = Math.abs(nums[i]);
            if (num <= nums.length) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        // 3. 遍历数组，寻找标记，如果index对应的值为正，则表示数组中没有出现过index
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }
}
